package sort;

import java.util.Arrays;

//快速排序
public class QuickSort2 {
    public static void main(String[] args) {
        int ary[] = {1, 3, 9, 56, 87, 49, 35};
        System.out.println(Arrays.toString(ary));
        System.out.println();

        quickSort(ary, 0, ary.length - 1);
        System.out.println(Arrays.toString(ary));
        System.out.println();
    }

    public static void quickSort(int[] ary, int start, int end) {
        //表示枢纽元位置的元素值
        int pivot = ary[end];

        //x表示左侧区域的最大下标，默认在当前需要处理的数组片段的最左侧
        int x = start;
        //y表示右侧区域的最小下标，默认在当前需要处理的数组片段的最右侧
        int y = end;

        //y会递减，x会递增，当x < y时循环
        while (x < y) {
            //从右至左找出大于枢纽元的元素，并标记位置，当指向的元素
            //小于或等于枢纽元时，跳出循环
            while (x < y && ary[y] > pivot) {
                y--;
            }

            //从左至右找出小于枢纽元的元素，并标记位置，当指向的元素
            //大于或等于枢纽元时，跳出循环
            while (x < y && ary[x] < pivot) {
                x++;
            }

            //判断现在x与y指向的元素是否与枢纽元的大小相同
            if (x < y && ary[x] == ary[y]) {
                //x与y指向的元素与枢纽元的大小相同，x继续向右移动，否则会卡死
                x++;
            } else {
                //x与y指向的不是枢纽元，但x指向的元素大于或等于枢纽元，
                //y指向的元素小于或等于枢纽元，则需要换位
                int temp = ary[x];
                ary[x] = ary[y];
                ary[y] = temp;
            }

            //如果左侧或右侧区域仍有元素，则递归
            if (x - 1 > start) {
                quickSort(ary, start, x - 1);
            }
            if (y + 1 < end) {
                quickSort(ary, y + 1, end);
            }
        }
    }
}
